//删除链表中重复的结点:  https://www.nowcoder.com/practice/fc533c45b73a41b0b44ccba763f866ef?
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
  public:
    ListNode* deleteDuplication(ListNode* pHead) {
        if (nullptr == pHead) 
        {
            return pHead;
        }
        //考虑到与可能全部相同，带个头结点更简单
        ListNode* head = new ListNode(0);
        head->next = pHead;
        //prev 永远 在 last的前面
        ListNode* prev = head;
        ListNode* last = prev->next;
        while (last != nullptr) 
        {
            //1. 如果last和last->next不相等，就一直让prev和last往后走，先找到重复的开始
            while (last->next != nullptr && last->val != last->next->val) 
            {
                prev = prev->next;
                last = last->next;
            }
            //2. 如果如果last和last->next相等，就让last一直往后走，在找到重复的范围
            while (last->next != nullptr && last->val == last->next->val) 
            {
                last = last->next;
            }
            //走到这里结果一共有三种,注意：prev永远指向的是前驱有效节点：
            //1. last->next != nullptr 并且 (prev, last] 限定了一段重复范围，此时进行去重
            //2. last->next == nullptr && (prev, last] 限定了一段重复范围，此时进行去重，最后相当于
            prev->next = nullptr;
            //3. last->next == nullptr && prev->next == last,这说明，从本次循环开始，大家都不相同,就不需要进行去重，这个是特殊情况
            if (prev->next != last) 
            {
                prev->next = last->next;
            }
            last = last->next;
        }
        return head->next;
    }
};